package com.zhupf.part6;

/**
 * @author zhupf
 * @date 2024年11月21日 10:05
 * @Description 240. 搜索二维矩阵 II
 * 中等
 * 相关标签
 * 相关企业
 * 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
 * <p>
 * 每行的元素从左到右升序排列。
 * 每列的元素从上到下升序排列
 */
public class SearchMatrix {

    public static void main(String[] args) {
        int[][] matrix = {{1}, {1}};
        System.out.println(searchMatrix(matrix, 2));
    }

    public static boolean searchMatrix(int[][] matrix, int target) {
        int n1 = matrix.length;
        int n2 = matrix[0].length;
        int i = n2 - 1;
        int j = 0;
        for (; i >= 0 && j < n1; ) {
            if (matrix[j][i] == target) {
                return true;
            }
            if (matrix[0][i] < target) {
                for (; j < n1 && i >= 0; ) {
                    if (matrix[j][i] == target) {
                        return true;
                    }
                    if (matrix[j][i] > target) {
                        break;
                    }
                    j++;
                }
            }
            i--;
        }
        return false;
    }

}
